如果你做过 P4358 [CQOI2016]密钥破解 ，那么你基本上就凉了。
这道题跟背景没有任何关系。
注意到二元不定方程：
又因为
那么:
可以用扩欧求出一组特解 。
当指数小于零时用逆元代替。
#include <cstdio>
using namespace std;
#define LL long long
template<typename _T>
void Read( _T &x ) {
x = 0; int f = 1;
char s = getchar( );
for( ; s < '0' || s > '9' ; s = getchar( ) ) f = s == '-' ? -f : f;
for( ; s >= '0' && s <= '9' ; s = getchar( ) ) x = x * 10 + s - '0';
x *= f;
}
template<typename _T>
void Write( _T x ) {
if( x < 0 ) putchar( '-' ) , x = -x;
if( x >= 10 ) Write( x / 10 );
putchar( x % 10 + '0' );
}
LL N , c1 , c2 , e1 , e2;
LL x , y;
LL Exgcd( LL a , LL b , LL &x , LL &y ) {
if( !b ) {
x = 1 , y = 0;
return a;
}
LL r = Exgcd( b , a % b , y , x );
y -= ( a / b ) * x;
return r;
}
LL Inv( LL x , LL p ) {
LL u , v;
Exgcd( x , p , u , v );
return ( u % p + p ) % p;
}
LL Quick_mul( LL x , LL po , LL Mod ) {
LL Ans = 0;
for( ; po ; po >>= 1 , x = ( x + x ) % Mod )
if( po & 1 ) Ans = ( Ans + x ) % Mod;
return Ans;
}
LL Quick_pow( LL x , LL po , LL Mod ) {
if( po < 0 ) x = Inv( x , Mod ) , po = -po;
LL Ans = 1;
for( ; po ; po >>= 1 , x = Quick_mul( x , x , Mod ) )
if( po & 1 ) Ans = Quick_mul( Ans , x , Mod );
return Ans;
}
int main( ) {
// freopen("D.in","r",stdin);
// freopen("D.out","w",stdout);
int t; Read( t );
while( t -- ) {
Read( c1 ) , Read( c2 ) , Read( e1 ) , Read( e2 ) , Read( N );
Exgcd( e1 , e2 , x , y );
Write( Quick_mul( Quick_pow( c1 , x , N ) , Quick_pow( c2 , y , N ) , N ) ) , putchar('\n');
}
return 0;
}